//
//  Problem349.swift
//  TestProject
//
//  Created by 毕武侠 on 2021/5/5.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 349. 两个数组的交集
 给定两个数组，编写一个函数来计算它们的交集。

 示例 1：
     输入：nums1 = [1,2,2,1], nums2 = [2,2]
     输出：[2]
 示例 2：
     输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
     输出：[9,4]
 说明：
     输出结果中的每个元素一定是唯一的。
     我们可以不考虑输出结果的顺序。
 */
@objcMembers class Problem349: NSObject {
    func solution() {
        print(intersectionDPoint([1,2,2,1], [2,2]))
        print(intersectionDPoint([4,9,5], [9,4,9,8,4]))
    }
    
    /*
     暴力破解：
     双层循环
     */
    func intersection(_ nums1: [Int], _ nums2: [Int]) -> [Int] {
        var result:[Int] = []
        for n1 in nums1 {
            if nums2.contains(n1), result.contains(n1) == false {
                result.append(n1)
            }
        }
        return result
    }
    
    /*
     优化：
     Set去重
     */
    func intersectionSet(_ nums1: [Int], _ nums2: [Int]) -> [Int] {
        let set1 = Set(nums1)
        let set2 = Set(nums2)
        var result:Set<Int> = []
        for n1 in set1 {
            if set2.contains(n1) {
                result.insert(n1)
            }
        }
        return Array(result)
    }
    
    /*
     双指针：
     1: 先把2个数组排序，
     2: 创建2个指针i，j指向排序后的数组
     3: 开始遍历，如果n1[i] == n2[j] 则：i++ j++, 否则小的那个++
     */
    func intersectionDPoint(_ nums1: [Int], _ nums2: [Int]) -> [Int] {
        let list1 = nums1.sorted()
        let list2 = nums2.sorted()
        var result:Set<Int> = []
        
        var i = 0
        var j = 0
        while i < nums1.count && j < nums2.count {
            if list1[i] == list2[j] {
                result.insert(list1[i])
                i += 1
                j += 1
            } else if list1[i] < list2[j] {
                i += 1
            } else {
                j += 1
            }
        }
        
        return Array(result)
    }
}
